home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / compress / misc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-16  |  9.8 KB  |  421 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. /*
  4.  * misc.c:    Miscellaneous routines used everywhere.
  5.  */
  6.  
  7. #include "defs.h"
  8.  
  9. #define MYEOF    0xffffffff
  10.  
  11. /*
  12.  * These are the global variables common to both compress/uncompress/csearch.c
  13.  */
  14.  
  15. int RESERVED_CHARS;
  16. int MAX_WORDS;
  17. int SPECIAL_WORDS;
  18. int BEGIN_SPECIAL_WORDS;
  19. int END_SPECIAL_WORDS;
  20. int NUM_SPECIAL_DELIMITERS;
  21. int END_SPECIAL_DELIMITERS;
  22. int ONE_VERBATIM;
  23. int TC_FOUND_NOTBLANK;
  24. int TC_FOUND_BLANK;
  25. int usemalloc = 0;
  26.  
  27. char special_texts[] = SPECIAL_TEXTS;
  28. char special_delimiters[] = SPECIAL_DELIMITERS;
  29.  
  30. hash_entry freq_words_table[MAX_WORD_LEN+2][256];        /* 256 is the maximum possible number of special words */
  31. char freq_words_strings[256][MAX_WORD_LEN+2];
  32. int freq_words_lens[256];
  33.  
  34. set_usemalloc()
  35. {
  36.     usemalloc = 1;
  37. }
  38.  
  39. unset_usemalloc()
  40. {
  41.     usemalloc = 0;
  42. }
  43.  
  44. unsigned int
  45. mygetc(fp, buf, maxlen, lenp)
  46.     FILE    *fp;
  47.     unsigned char    *buf;
  48.     int    *lenp;
  49. {
  50.     unsigned int    c;
  51.  
  52.     if (fp != NULL) c = getc(fp);
  53.     if (buf != NULL) {
  54.         if (*lenp >= maxlen) return MYEOF;
  55.         else c = (unsigned int)buf[*lenp];
  56.     }
  57.     (*lenp) ++;
  58.     return c;
  59. }
  60.  
  61. myfpcopy(fp, src)
  62.     FILE    *fp;
  63.     char    *src;
  64. {
  65.     int i=0;
  66.  
  67.     while(*src) {
  68.         putc(*src, fp);
  69.         src ++;
  70.         i ++;
  71.     }
  72.     return i;
  73. }
  74.  
  75. mystrcpy(dest, src)
  76.     char    *src, *dest;
  77. {
  78.     int i=0;
  79.  
  80.     while(*dest = *src) {
  81.         dest ++;
  82.         src ++;
  83.         i ++;
  84.     }
  85.     return i;
  86. }
  87.  
  88. /* Returns 1 if little endian, 0 if big endian */
  89. int
  90. get_endian()
  91. {
  92.     union{
  93.         int    x;
  94.         struct    {
  95.             short    y1;
  96.             short    y2;
  97.         } y;
  98.     } var;
  99.  
  100.     var.x = 0xffff0000;
  101.     if (var.y.y1 == 0) return 1;
  102.     else return 0;
  103. }
  104.  
  105. /*
  106.  * These procedures take care of the fact that the msb of the encoded
  107.  * short cannot be < RESERVED_CHARS, and the lsb cannot be equal to '\n' or '\0'.
  108.  */
  109.  
  110. unsigned char
  111. encode_msb(i)
  112.     unsigned char    i;
  113. {
  114.     return i + RESERVED_CHARS;
  115. }
  116.  
  117. unsigned char
  118. decode_msb(i)
  119.     unsigned char    i;
  120. {
  121.     return i - RESERVED_CHARS;
  122. }
  123.  
  124. unsigned char
  125. encode_lsb(i)
  126.     unsigned char    i;
  127. {
  128.     if (i == '\0') return MAX_LSB;
  129.     if (i == '\n') return MAX_LSB + 1;
  130.     return i;
  131. }
  132.  
  133. unsigned char
  134. decode_lsb(i)
  135.     unsigned char    i;
  136. {
  137.     if (i == MAX_LSB) return '\0';
  138.     if (i == MAX_LSB + 1) return '\n';
  139.     return i;
  140. }
  141.  
  142. unsigned short
  143. encode_index(i)
  144.     unsigned short    i;
  145. {
  146.     unsigned char msb, lsb;
  147.  
  148.     msb = (i / MAX_LSB);
  149.     lsb = (i % MAX_LSB);
  150.     msb = encode_msb(msb);
  151.     lsb = encode_lsb(lsb);
  152.     return (msb << 8) | lsb;
  153. }
  154.  
  155. unsigned short
  156. decode_index(i)
  157.     unsigned short    i;
  158. {
  159.     unsigned char msb, lsb;
  160.  
  161.     msb = ((i & 0x0ff00) >> 8);
  162.     lsb = (i & 0x00ff);
  163.     msb = decode_msb(msb);
  164.     lsb = decode_lsb(lsb);
  165.     return (msb * MAX_LSB + lsb);
  166. }
  167.  
  168. #if    0
  169. /* This is bullshit */
  170.  
  171. unsigned short
  172. encode_index(i)
  173.     unsigned short    i;
  174. {
  175.     unsigned int msb, lsb;
  176.  
  177. top:
  178.     msb = (i & 0xff00) >> 8;
  179.     if ((i & 0x00ff) == '\n') { i = MAX_WORDS + msb; goto top; /* eliminate tail recursion */}
  180.     lsb = (i & 0x00ff);
  181.     msb += RESERVED_CHARS;
  182.     return (0x0000ffff & ((msb << 8) | lsb));
  183. }
  184.  
  185. unsigned short
  186. decode_index(i)
  187.     unsigned short    i;
  188. {
  189.     unsigned int msb, lsb, ret;
  190.  
  191.     msb = (i & 0xff00) >> 8;
  192.     lsb = (i & 0x00ff);
  193.     msb -= RESERVED_CHARS;
  194.     ret = (0x0000ffff & ((msb << 8) | lsb));
  195.     if (ret >= MAX_WORDS) ret = (((ret - MAX_WORDS) << 8) | '\n');
  196.     return ret;
  197. }
  198. #endif    /*0*/
  199.  
  200. char    comp_signature[SIGNATURE_LEN];    /* SIGNATURE_LEN - 1 hex-chars terminated by '\0' */
  201.  
  202. /* returns the number of words read */
  203. build_freq(freq_words_table, freq_words_strings, freq_words_lens, freq_file, flags)
  204.     hash_entry    freq_words_table[MAX_WORD_LEN+2][256];
  205.     char        freq_words_strings[256][MAX_WORD_LEN+2];
  206.     int        freq_words_lens[256];
  207.     char        *freq_file;
  208. {
  209.     FILE    *fp = fopen(freq_file, "r");
  210.     int    len, num, i, j;
  211.     hash_entry    *e;
  212.     int    numsofar = 0;
  213.     int    freq_words;
  214.  
  215.     memset(comp_signature, '\0', SIGNATURE_LEN);
  216.     if (fp == NULL) {
  217.         if (flags & TC_ERRORMSGS) {
  218.             fprintf(stderr, "cannot open cast-dictionary file: %s\n", freq_file);
  219.             fprintf(stderr, "(use -H to give a dictionary-dir or run 'buildcast' to make a dictionary)\n");
  220.         }
  221.         return -1;
  222.     }
  223.  
  224.     /* initialize the tables by accessing only those entries which will be used */
  225.     if (SIGNATURE_LEN != fread(comp_signature, 1, SIGNATURE_LEN, fp)) {
  226.         if (flags & TC_ERRORMSGS) fprintf(stderr, "illegal cast signature in: %s\n", freq_file);
  227.         fclose(fp);
  228.         return -1;
  229.     }
  230.     comp_signature[SIGNATURE_LEN - 1] = '\0';    /* overwrite '\0' */
  231.     fscanf(fp, "%d\n", &freq_words);
  232.     if ((freq_words < 0) || (freq_words > 256 - MAX_SPECIAL_CHARS)) {
  233.         if (flags & TC_ERRORMSGS) fprintf(stderr, "illegal number of frequent words %d outside [0, %d] in: %s\n", freq_words, 256-MAX_SPECIAL_CHARS, freq_file);
  234.         fclose(fp);
  235.         return -1;
  236.     }
  237.     if (freq_words == 0) {
  238.         fclose(fp);
  239.         return 0;
  240.     }
  241.     for (i=0; i<=MAX_WORD_LEN; i++) {
  242.         for (j=0; j<freq_words; j++)
  243.             freq_words_table[i][j].val.offset = -1;
  244.     }
  245.     memset(freq_words_lens, '\0', sizeof(int)*freq_words);
  246.     for (i=0; i<freq_words; i++) {
  247.         freq_words_strings[i][0] = '\0';
  248.     }
  249.  
  250.     /* Refer to read_in.c for the format in which these words are dumped */
  251.     while (2 == fscanf(fp, "%d %d\n", &len, &num)) {
  252.         for(i=0; i<num; i++) {
  253.             e = &(freq_words_table[len][i]);
  254.             e->word = &(freq_words_strings[numsofar + i][0]);
  255.             if (1 != fscanf(fp, "%s\n", e->word)) {
  256.                 fclose(fp);
  257.                 return numsofar;
  258.             }
  259.             freq_words_lens[numsofar + i] = len;
  260.             e->val.offset = numsofar + i;    /* which-th special word is it? */
  261.             if (i + 1 == num)
  262.                 e->next = NULL;
  263.             else e->next = &(freq_words_table[len][i+1]);
  264.         }
  265.         numsofar += num;
  266.     }
  267.     fclose(fp);
  268.     return numsofar;
  269. }
  270.  
  271. int    initialize_common_done = 0;
  272.  
  273. /* Used in tcomp.c, tuncomp.c and csearch.c */
  274. initialize_common(freq_file, flags)
  275. char    *freq_file;
  276. int    flags;
  277. {
  278.     if (initialize_common_done == 1) return 1;
  279.         if ((SPECIAL_WORDS = build_freq(freq_words_table, freq_words_strings, freq_words_lens, freq_file, flags)) == -1) return 0;
  280.         BEGIN_SPECIAL_WORDS = MAX_SPECIAL_CHARS;
  281.         RESERVED_CHARS = END_SPECIAL_WORDS = BEGIN_SPECIAL_WORDS + SPECIAL_WORDS;
  282.         MAX_WORDS = MAX_LSB*(256-RESERVED_CHARS);    /* upper byte must be > RESERVED_CHARS, lower byte must not be '\n' */
  283.     TC_FOUND_NOTBLANK = 0;
  284.     TC_FOUND_BLANK = 0;
  285.     initialize_common_done = 1;
  286.     return 1;
  287. }
  288.  
  289. uninitialize_common()
  290. {
  291.     initialize_common_done = 0;
  292.     return;
  293. }
  294.  
  295. /*
  296.  * Simple O(worlen*linelen) search since the average linelen is
  297.  * guaranteed to be ~ 80/2, and the average wordlen, 2.
  298.  * SHOULD WORK FOR ANY LEGITIMATE COMPRESSED STRING WITH EASY SEARCH
  299.  */
  300. int
  301. exists_tcompressed_word(word, wordlen, line, linelen, flags)
  302.     CHAR    *word, *line;
  303.     int    wordlen, linelen;
  304. {
  305.     int    i, j;
  306.  
  307. #if    0
  308.     for (i=0; i<linelen; i++) printf("%d ", line[i]);
  309.     printf("\n");
  310.     for (i=0; i<wordlen; i++) printf("%d ", word[i]);
  311.     printf("\n");
  312. #endif    /*0*/
  313.  
  314.     if (wordlen > linelen) return -1;
  315.     if (flags & TC_EASYSEARCH) {
  316.         for (i=0; i<=linelen-wordlen; i++) {
  317.             if (word[0] == BEGIN_VERBATIM)
  318.                 while ((i <= linelen - wordlen) && (line[i] != BEGIN_VERBATIM)) i++;
  319.             j = 0;
  320.             while ((j < wordlen) && (i <= linelen - wordlen) && (word[j] == line[i+j])) j++;
  321.             if (j >= wordlen) return i;
  322.             if (i > linelen - wordlen) return -1;
  323.  
  324.             /* Goto next-pos for i. Remember: the for loop ALSO skips over one i */
  325.             if (line[i] >= RESERVED_CHARS) i++;
  326.             else if (line[i] == BEGIN_VERBATIM) {
  327.                 i++;
  328.                 while ((i <= linelen - wordlen) && (line[i] != END_VERBATIM)) i++;
  329.                 if (i > linelen - wordlen) return -1;
  330.             }
  331.             else if (line[i] == EASY_ONE_VERBATIM) i++;
  332.         }
  333.     }
  334.     else {
  335.         for (i=0; i<=linelen-wordlen; i++) {
  336.             if (word[0] == BEGIN_VERBATIM)
  337.                 while ((i <= linelen - wordlen) && (line[i] != BEGIN_VERBATIM)) i++;
  338.             j = 0;
  339.             while ((j < wordlen) && (i <= linelen - wordlen) && (word[j] == line[i+j])) j++;
  340.             if (j >= wordlen) return i;
  341.             if (i > linelen - wordlen) return -1;
  342.  
  343.             /* Goto next-pos for i. Remember: the for loop ALSO skips over one i */
  344.             if (line[i] >= RESERVED_CHARS) i++;
  345.             else if (line[i] == BEGIN_VERBATIM) {
  346.                 i++;
  347.                 while ((i <= linelen - wordlen) && (line[i] != BEGIN_VERBATIM) && (line[i] != END_VERBATIM)) i++;
  348.                 if (i > linelen - wordlen) return -1;
  349.                 if (line[i] == BEGIN_VERBATIM) i--;    /* counter-act the i++ */
  350.             }
  351.         }
  352.     }
  353.  
  354.     return -1;
  355. }
  356.  
  357. /*
  358.  * There is a problem here if we use these two routines to search for delimiters:
  359.  * With outtail set, the implicit blank AFTER the word just before the beginning
  360.  * of the record and a possible NOTBLANK after the end of the record might be missed.
  361.  * No way to rectify it now unless we have flags to indicate if these things occured.
  362.  * That is why, I have introduced TC_FOUND_NOTBLANK and TC_FOUND_BLANK.
  363.  */
  364.  
  365. /* return where the word begins or ends (=outtail): range = [begin, end) */
  366. unsigned char *
  367. forward_tcompressed_word(begin, end, delim, len, outtail, flags)
  368.     unsigned char *begin, *end, *delim;
  369.     int len, outtail, flags;
  370. {
  371.     register unsigned char *curend;
  372.     register int pos;
  373.  
  374.     TC_FOUND_NOTBLANK = 0;
  375.     if (begin + len > end) return end + 1;
  376.     curend = begin;
  377. top:
  378.     while ((curend <= end) && (*curend != '\n')) curend ++;
  379.     if ((pos = exists_tcompressed_word(delim, len, begin, curend-begin, flags)) == -1) {
  380.         curend ++;    /* for next '\n' */
  381.         if (curend > end) return end + 1;
  382.         begin = curend;
  383.         goto top;
  384.     }
  385.     begin += pos;    /* place where delimiter begins */
  386.     if (outtail) {
  387.         TC_FOUND_NOTBLANK = 1;
  388.         return begin + len;
  389.     }
  390.     else return begin;
  391. }
  392.  
  393. /* return where the word begins or ends (=outtail): range = [begin, end) */
  394. unsigned char *
  395. backward_tcompressed_word(end, begin, delim, len, outtail, flags)
  396.     unsigned char *begin, *end, *delim;
  397.     int len, outtail, flags;
  398. {
  399.     register unsigned char *curbegin;
  400.     register int pos;
  401.  
  402.     TC_FOUND_BLANK = 0;
  403.     if (begin + len > end) return begin;
  404.     curbegin = end;
  405. top:
  406.     while ((curbegin > begin) && (*curbegin != '\n')) curbegin --;
  407.     if ((pos = exists_tcompressed_word(delim, len, curbegin, end-curbegin, flags)) == -1) {
  408.         curbegin --;    /* for next '\n' */
  409.         if (curbegin < begin) return begin;
  410.         end = curbegin;
  411.         goto top;
  412.     }
  413.     curbegin += pos;    /* place where delimiter begins */
  414.     if (outtail) {
  415.         if ((curbegin + len < end) && (*(curbegin + len) != NOTBLANK)) TC_FOUND_BLANK = 1;
  416.         return curbegin + len;
  417.     }
  418.     else return curbegin;
  419. }
  420.  
  421.